Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 83/115

Q: What is order of resultant heap after merging two tree of order k?
A. 2*k
B. k+1
C. k*k
D. k+logk
Solution: This could be easily verified by looking at the structure of a binomial heap.
Q: Time taken in decreasing the node value in a binomial heap is
A. O(n)
B. O(1)
C. O(logn)
D. O(nlogn)
Solution: Decreasing a node value may result in violating the min property. As a result be there would be exchange in the value of parent and child which at max goes up to height of the heap.
Q: What does this pseudo_code return ?

	int myfun(heap_arr[])
	{
		int mini=INF;
		for(int i=0;i
A. Last added element to heap
B. First element added to heap
C. Root of the heap
D. Leftmost node of the heap
Solution: The function return minimum value in the heap_Array which is equal to the root value of the heap.
Q: Which of these operations have same complexities?
A. Insertion, find_min
B. Find_min, union
C. Union, Insertion
D. Deletion, Find _max
Solution: With proper implementation using link list find_min and find_max operation can be done in O(1), while the remaining takes O(logn) time.
Q: Given a heap of n nodes.The maximum number of tree for building the heap is.
A. n
B. n-1
C. n/2
D. logn
Solution: Each node could be seen as a tree with only one node and as a result maximum subtree in the heap is equal to number of nodes in the heap.
Q: Choose the option with function having same complexity for a fibonacci heap.
A. Insertion, Union
B. Insertion, Deletion
C. extract_min, insertion
D. Union, delete
Solution: For a fibonacci heap insertion, union take O(1) while remaining take O(logn) time.
Q: What is wrong with the following code of insertion in fibonacci heap.
Choose the correct option

	FIB-INSERT(H, x)
	degree[x]= 0
	p[x]=  NIL
	child[x] =NIL
	left[x] =x
	right[x] =x
	mark[x] =FALSE
	concatenate the root list containing x with root list H 
	if min[H] = NIL or key[x] > key[min[H]]
	then min[H]= x
	n[H]= n[H] + 1
A. Line -11
B. Line -3
C. Line 9
D. Line 7
Solution: The main characterstics of a fibonacci heap is violated since min[H] must conatin one with smallest value.
Q: What will be the order of new heap created after union of heap H1 and H2 when created by the following code.Initially both are of the order n.

	FIB_UNION(H1,H2)
	{
		H =MAKE_HEAP()
		min[H]= min[H1]
		concatenate the root list of H2 with the root list of H
		if (min[H1] = NIL) or (min[H2]!= NIL and min[H2] < min[H1])
		then min[H] = min[H2]
		n[H]=  n[H1] + n[H2]
		free the objects H1 and H2
		return H
	}
A. n+1
B. n+n/2
C. nlogn
D. 2*n
Solution: Union of two trees increase the order of the resultant by atmost value 1.

You Have Score    /8